package basic.courseLearn16.problem;

import org.junit.Test;

//在一个x9y10的棋盘上，有一个马的棋子在（0，0）位置上，指定一个点（a，b），马需要走k步，问方法有多少种
public class ChessboardMove {

    @Test
    public void test_solution_1(){
        System.out.println(solution_1(9, 5, 0));
    }

    @Test
    public void test_solution_2(){
        int[][][] memo = new int[9][10][10];
        //初始化memo数组
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    memo[i][j][k] = -1;
                }
            }
        }

        System.out.println(solution_2(memo,0, 0, 2));
    }
    @Test
    public void test_solution_3(){
        System.out.println(solution_3(9, 5, 0));
    }

    @Test
    public void check(){
        int count = 1000; //测试次数
        int num_range = 10; //测试范围
        for (int i = 0; i < count; i++) {
            int x = (int)(Math.random() * num_range);
            int y = (int)(Math.random() * num_range);
            int power = (int)(Math.random() * num_range);
            int ways_1 = solution_1(x,y,power);
            int[][][] memo = new int[9][10][10];
            //初始化memo数组
            for (int k = 0; k < 9; k++) {
                for (int j = 0; j < 10; j++) {
                    for (int l = 0; l < 10; l++) {
                        memo[k][j][l] = -1;
                    }
                }
            }
            int ways_2 = solution_2(memo,x,y,power);
            int ways_3 = solution_3(x,y,power);
            if (ways_1!= ways_2 || ways_1!= ways_3){
                System.out.println("error");
                System.out.println("x="+x+",y="+y+",power="+power);
                System.out.println("ways_1="+ways_1+",ways_2="+ways_2 +",ways_3="+ways_3);
                break;
            }
        }
        System.out.println("测试完成");


    }


    /**
     * 方法1：暴力递归，枚举所有可能的走法，计算每种走法的步数，然后累计求和
     * @param x 当前位置的x坐标
     * @param y 当前位置的y坐标
     * @param power 马的体力值
     * @return 所有方法数
     */
    public int solution_1(int x,int y,int power){
        //1. 出界判断
        if(x<0 || x>=9 || y<0 || y>=10){
            return 0;
        }
        //2. 终止条件
        if (power < 0){
            return 0;
        }
        if (power == 0 && x ==0 && y == 0){
            return 1;
        }
        //3. 递归计算
        int ways = 0;
        ways += solution_1(x-1,y-2,power-1)+
                solution_1(x-2,y-1,power-1)+
                solution_1(x-2,y+1,power-1)+
                solution_1(x-1,y+2,power-1)+
                solution_1(x+1,y+2,power-1)+
                solution_1(x+2,y+1,power-1)+
                solution_1(x+2,y-1,power-1)+
                solution_1(x+1,y-2,power-1);
        return ways;
    }

    /**
     * 方法2：记忆表搜索
     * @param x 当前位置的x坐标
     * @param y 当前位置的y坐标
     * @param power 马的体力值
     * @return 所有方法数
     */
    public int solution_2(int[][][] memo,int x,int y,int power){
        //1. 出界判断
        if(x<0 || x>=9 || y<0 || y>=10){
            return 0;
        }
        //2. 终止条件
        if (power < 0){
            return 0;
        }
        if (power == 0 && x ==0 && y == 0){
            return 1;
        }
        //3. 记忆表搜索
        if (memo[x][y][power] != -1){
            return memo[x][y][power];
        }

        //4. 递归计算
        int ways = 0;
        ways += solution_2(memo,x-1,y-2,power-1)+
                solution_2(memo,x-2,y-1,power-1)+
                solution_2(memo,x-2,y+1,power-1)+
                solution_2(memo,x-1,y+2,power-1)+
                solution_2(memo,x+1,y+2,power-1)+
                solution_2(memo,x+2,y+1,power-1)+
                solution_2(memo,x+2,y-1,power-1)+
                solution_2(memo,x+1,y-2,power-1);
        memo[x][y][power] = ways;
        return ways;
    }

    /**
     * 方法3：严格表结构
     * @param x 当前位置的x坐标
     * @param y 当前位置的y坐标
     * @param power 马的体力值
     * @return 所有方法数
     */
    public int solution_3(int x,int y,int power){
        //0. 边界条件
        if (x<0 || x>=9 || y<0 || y>=10 || power<0){
            return 0;
        }
        //1. 初始化严格表
        int[][][] memo = new int[9][10][power+1];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 10; j++) {
                if (i == 0 && j == 0){
                    memo[i][j][0] = 1;
                }else{
                    memo[i][j][0] = 0;
                }
            }
        }
        //2. 根据公式逐层计算
        for (int k = 1; k <= power; k++) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 10; j++) {
                    memo[i][j][k] =
                            (((i-1>=0) && (j-2>=0) & (k-1<=power))?memo[i-1][j-2][k-1]:0)+
                            (((i-2>=0) && (j-1>=0)& (k-1<= power))?memo[i-2][j-1][k-1]:0)+
                            (((i-2>=0) && (j+1<10)& (k-1<= power))?memo[i-2][j+1][k-1]:0)+
                            (((i-1>=0) && (j+2<10)& (k-1<= power))?memo[i-1][j+2][k-1]:0)+
                            (((i+1<9) && (j+2<10)& (k-1<=power))?memo[i+1][j+2][k-1]:0)+
                            (((i+2<9) && (j+1<10)& (k-1<=power))?memo[i+2][j+1][k-1]:0)+
                            (((i+2<9) && (j-1>=0)& (k-1<=power))?memo[i+2][j-1][k-1]:0)+
                            (((i+1<9) && (j-2>=0)& (k-1<=power))?memo[i+1][j-2][k-1]:0);
                }
            }
        }
        //3. 计算结果
        return memo[x][y][power];

    }

}
